home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / node_pq.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.9 KB  |  75 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  node_pq.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_NODE_PQ_H
  17. #define LEDA_NODE_PQ_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // node priority queues
  21. //------------------------------------------------------------------------------
  22.  
  23. #include <LEDA/graph.h>
  24. #include <LEDA/impl/bin_heap.h>
  25.  
  26.  
  27. #define PRIO_IMPL bin_heap
  28. #define PRIO_ITEM bin_heap_item
  29.  
  30. template <class itype>
  31.  
  32. class _CLASSTYPE node_pq : private PRIO_IMPL
  33. {
  34.  
  35. int cmp(GenPtr x, GenPtr y)  const
  36.                          { return compare(ACCESS(itype,x),ACCESS(itype,y)); }
  37. void print_key(GenPtr x)    const { Print(ACCESS(itype,x)); }
  38. void print_inf(GenPtr x)    const { Print(GenPtr(x));  }
  39. void clear_key(GenPtr& x)   const { Clear(ACCESS(itype,x)); }
  40. void copy_key(GenPtr& x)    const { x=Copy(ACCESS(itype,x));  }
  41.  
  42. int  int_type()             const { return INT_TYPE(itype); }
  43.  
  44. public:
  45.  node_pq(const graph&) { }
  46. ~node_pq()             { clear(); }
  47.  
  48. void decrease_inf(node v, itype i)
  49. { PRIO_IMPL::decrease_key(PRIO_ITEM(v->data[1]),Convert(i)); }
  50.  
  51. void insert(node v,itype i)
  52. { v->data[1] = PRIO_IMPL::insert(Convert(i),v);}
  53.  
  54. itype inf(node v) const
  55. { return ACCESS(itype,PRIO_IMPL::key((PRIO_ITEM)v->data[1])); }
  56.  
  57. void del(node v) 
  58. { PRIO_IMPL::del_item(PRIO_ITEM(v->data[1])); }
  59.  
  60. node find_min() const  
  61. { return (node)PRIO_IMPL::inf(PRIO_IMPL::find_min());   }
  62.  
  63. node del_min()   
  64. { node v = find_min(); PRIO_IMPL::del_min(); return v; }
  65.  
  66. void clear()     { PRIO_IMPL::clear(); }
  67.  
  68. int size()   const { return PRIO_IMPL::size(); }
  69. int empty()  const { return PRIO_IMPL::empty(); }
  70.  
  71. };
  72.  
  73.  
  74. #endif
  75.